package it.storm.solution;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 118. 杨辉三角
 * https://leetcode-cn.com/problems/pascals-triangle/
 */
public class Solutions_118 {
    public static void main(String[] args) {
        int numRows = 5;  // output: {{1}, {1, 1}, {1, 2, 1}, {1, 3, 3, 1}, {1, 4, 6, 4, 1}}
        List<List<Integer>> result = generate(numRows);
        System.out.println(result);
    }

    public static List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        if (numRows < 1) {
            return res;
        }
        Integer[][] dp = new Integer[numRows][];
        for (int i = 0; i < numRows; i++) {
            // 第 i 行，有 count 个元素
            int count = i + 1;
            dp[i] = new Integer[count];

            for (int j = 0; j < count; j++) {
                if (j == 0 || j == count - 1) {
                    // 每行，第一位与最后一位都是 1
                    dp[i][j] = 1;
                } else if (i > 0) {
                    // 除第 1 行，以及其他行的第 1 位与最后 1 位，其余数都是上一行的左上方和右上方的数的和
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                }
            }
        }
        for (Integer[] arr : dp) {
            res.add(Arrays.asList(arr));
        }
        return res;
    }
}
